from typing import List

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        """
        递归+记忆化搜索，解决大礼包最优购买问题
        :param price: 单品价格列表
        :param special: 大礼包列表，每个礼包前n项为商品数量，最后一项为礼包价格
        :param needs: 需求列表
        :return: 最低花费
        """
        memo = {}

        def dfs(cur_needs):
            if tuple(cur_needs) in memo:
                return memo[tuple(cur_needs)]
            # 不买礼包，直接单买
            min_cost = sum(cur_needs[i] * price[i] for i in range(len(price)))
            # 尝试每个礼包
            for sp in special:
                new_needs = []
                for i in range(len(price)):
                    if cur_needs[i] < sp[i]:
                        break
                    new_needs.append(cur_needs[i] - sp[i])
                else:
                    # 如果礼包可用，递归计算剩余需求
                    min_cost = min(min_cost, dfs(new_needs) + sp[-1])
            memo[tuple(cur_needs)] = min_cost
            return min_cost

        return dfs(needs)